import java.util.*;

class Solution {
    //692. 前K个高频单词
    //给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。
    public List<String> topKFrequent(String[] words, int k) {
        HashMap<String, Integer> map = new HashMap<>();
        //保存字符串数组到map
        for (String x : words) {
            if (map.containsKey(x)) {
                int val = map.get(x);
                map.put(x, val + 1);
            } else {
                map.put(x, 1);
            }
        }
        //Top-K问题
        PriorityQueue<Map.Entry<String, Integer>> q1 =
                new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
                    @Override
                    public int compare(Map.Entry<String, Integer> o1,
                                       Map.Entry<String, Integer> o2) {
                        if (o1.getValue().compareTo(o2.getValue()) == 0) {
                            //频率相同,按照单词首字母大小建立大堆
                            return o2.getKey().compareTo(o1.getKey());
                        }//频率不同，按照频率大小建立小堆
                        return o1.getValue().compareTo(o2.getValue());
                    }
                });
        //遍历map当中的entry
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            //把前k个元素建成大堆
            if (q1.size() < k) {
                q1.offer(entry);
            } else {//后k个元素，逐渐和堆顶元素进行比较
                Map.Entry<String, Integer> s1 = q1.peek();
                //频率大
                if (entry.getValue().compareTo(s1.getValue()) > 0) {
                    //比堆顶元素大
                    //将堆顶元素出堆
                    q1.poll();
                    //再将这个元素入堆
                    q1.offer(entry);
                }//和堆顶元素频率相等
                else {
                    if (entry.getValue().compareTo(s1.getValue()) == 0) {
                        //比较单词首字母的大小
                        if (s1.getKey().compareTo(entry.getKey()) > 0) {
                            //比堆顶元素的首字母大，堆顶元素出堆，
                            q1.poll();
                            q1.offer(entry);
                        }
                    }
                }
            }
        }//将堆的元素赋值给List
        List<String> list = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            Map.Entry<String, Integer> m1 = q1.poll();
            list.add(m1.getKey());
        }
        Collections.reverse(list);
        return list;
    }

    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
        }
    }

    public Node copyRandomList(Node head) {
        HashMap<Node,Node> map=new HashMap<>();
        Node cur=head;
        //记录原来链表
        while(cur!=null){
            Node node=new Node(cur.val);
            map.put(cur,node);
            cur=cur.next;
        }
        cur=head;
        while(cur!=null){
            map.get(cur).next=map.get(cur.next);
            map.get(cur).random=map.get(cur.random);
            cur=cur.next;
        }
        return map.get(head);

    }
    //138. 复制带随机指针的链表
    //给你一个整数数组nums 和一个整数k ，
    // 判断数组中是否存在两个 不同的索引i和j ，
    // 满足 nums[i] == nums[j] 且 abs(i - j) <= k 。
    // 如果存在，返回 true ；否则，返回 false 。
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashMap <Integer,Integer> map=new HashMap<>();
        for(int i=0;i<nums.length;i++){
            if(map.containsKey(nums[i])){
                int value=map.get(nums[i]);
                int j=i;
                if(Math.abs(value-j)<=k){
                    return true;
                }else{
                    map.put(nums[i],i);
                }
            }else{
                map.put(nums[i],i);
            }
        }
        return false;
    }
    //给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，
    // 返回 true ；如果数组中每个元素互不相同，返回 false 。
    public boolean containsDuplicate(int[] nums) {
        HashMap<Integer,Integer> map=new HashMap<>();
        for (int i = 0; i < nums.length ; i++) {
            if(map.containsKey(nums[i])){
                int value=map.get(nums[i]);
                map.put(nums[i],value+1 );
                if(map.get(nums[i])>=2){
                    return  true;
                }
            }else{
                map.put(nums[i],1 );
            }
        }
        return  false;
    }
}